import math


class climbStairs:
    def climbStairs(self, n: int) -> int:
        raise NotImplementedError

class solution1(climbStairs):
    def climbStairs(self, n: int) -> int:
        p, q, r = 0, 0, 1
        for _ in range(n):
            p = q
            q = r
            r = p + q
        return r

class solution2(climbStairs):
    def climbStairs(self, n: int) -> int:
        q: list[list[int]] = [[1, 1], [1, 0]]
        res: list[list[int]] = self.pow(q, n)
        return res[0][0]

    def pow(self, a: list[list[int]], n: int) -> list[list[int]]:
        ret = [[1, 0], [0, 1]]
        while n > 0:
            if (n & 1) == 1:
                ret = self.multiply(a, ret)
            n >>= 1
            a = self.multiply(a, a)
        return ret

    def multiply(self, a: list[list[int]], b: list[list[int]]):
        c = [[0, 0], [0, 0]]
        for i in  range(2):
            for j in range(2):
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]
        return c

class solution3(climbStairs):
    def climbStairs(self, n: int) -> int:
        sqrt5 = math.sqrt(5)
        fibn = math.pow((1 + sqrt5) / 2, n + 1) - math.pow((1 - sqrt5) / 2, n + 1)
        return math.floor(fibn / sqrt5)
